"""
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。
你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
"""
import sys


# 只能买卖一次的动态规划
# 使用了一个结果操作法
def max_profit(prices: list[int]) -> int:
    profit = 0
    for i in range(1,len(prices)):
        if prices[i] > prices[i-1]:
            profit = profit + (prices[i]-prices[i-1])
    return profit


# 动态规划算法
def max_profit01(prices: list[int]) -> int:
    n = len(prices)
    dp0 = 0
    dp1 = -prices[0]
    for i in range(n):
        newDp0=max(dp0,dp1 + prices[i])
        newDp1=max(dp1,dp0-prices[i])
        dp0 = newDp0
        dp1 = newDp1
    return dp0

if __name__ == '__main__':
    prices = [2,1,2,0,1]
    print(max_profit01(prices))
